#define _CRT_SECURE_NO_WARNINGS 1

#pragma once
#include<iostream>

template<class K>
struct BS_nodetree
{
	K _key;
	BS_nodetree<K>* _left;
	BS_nodetree<K>* _right;
	BS_nodetree(const K& key = 0)
		:_key(key)
		, _left(nullptr)
		, _right(nullptr)
	{ }
};


template<class K>
class BStree
{
public:
	typedef BS_nodetree<K> node;

	bool insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new node;
			_root->_key = key;
			return true;
		}
		node* parent = nullptr;
		node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
				return false;
		}
		cur = new node(key);
		cur->_key = key;
		if (key < parent->_key)
			parent->_left = cur;
		else
			parent->_right = cur;
	}

	bool find(const K& key)
	{
		node* cur = this->_root;
		while (cur)
		{
			if (key == cur->_key)
				return true;
			else if (key < cur->_key)
				cur = cur->_left;
			else
				cur = cur->_right;
		}
		return false;
	}
	void Inorder()
	{
		_Inorder(_root);
	}

private:
	void _Inorder(node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_Inorder(root->_left);
		cout << root->_key;
		_Inorder(root->_right);
	}
	node* _root = nullptr;
};